package com.zang.stackqueue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 滑动窗口最大值
 * @author ZVerify
 * @since 2022/10/19 15:31
 * @see <a href="https://leetcode.cn/problems/sliding-window-maximum/">...</a>
 **/
// 单调队列
class MyQueue{

     Deque<Integer> deque = new LinkedList<>();

     void poll(int val){

         if (!deque.isEmpty() && deque.peek()==val){
             deque.poll();

         }
     }

     void add(int val){
        while (!deque.isEmpty() && deque.peekLast() < val) deque.pollLast();
        deque.add(val);
     }

     int peek(){
         return deque.peek();
     }





}
public class 滑动窗口最大值 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ints = new int[nums.length-k+1];

        MyQueue queue = new MyQueue();

        for (int i = 0;i<k;i++){
            queue.add(nums[i]);
        }

        int index = 0;
        ints[index++] = queue.peek();
        for (int i = k;i<nums.length;i++){
            queue.poll(nums[i-k]);
            queue.add(nums[i]);
            nums[index++] = queue.peek();
        }
        return nums;
    }

}
